home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Libraries / ravlf 2.1 / ravlf.c next >
Encoding:
Text File  |  1995-09-20  |  64.4 KB  |  1,574 lines  |  [TEXT/KAHL]
  1. *******************************************************************/
  2.  
  3. void Dispose_bRec(bnode_iType index)
  4. {
  5.     bRecType        bRec;
  6.     
  7.     Init_bRec(&bRec);
  8.     bRec.child[0] = header.free_bList;
  9.     header.free_bList = index;
  10.     Write_bRec(index, &bRec);
  11. } // Dispose_bRec
  12.  
  13.  
  14.  
  15. /*******************************************************************************
  16.  * Search1_BTree
  17.  *
  18.  *******************************************************************************/
  19.  
  20. data_iType Search1_BTree(bnode_iType root1, Key_Type *key)
  21. {
  22.     bRecType        bRec;
  23.     short            loop;
  24.     data_iType        result;
  25.     
  26.     if (root1 == NIL)
  27.     {
  28.         result = NIL;
  29.         *key = nokey;
  30.     }
  31.     else
  32.     {
  33.         Read_bRec(root1, &bRec);
  34.         loop = 0;
  35.         while ((loop < bRec.keyCount) && (*key > bRec.key[loop]))
  36.             loop++;
  37.         if ((loop < bRec.keyCount) && (*key == bRec.key[loop]))
  38.             result = bRec.data[loop];
  39.         else
  40.         {
  41.             result = Search1_BTree(bRec.child[loop], key);
  42.             if ((*key == nokey) && (loop < bRec.keyCount))
  43.                 *key = bRec.key[loop];
  44.         }
  45.     }
  46.     return result;
  47. } // Search1_BTree
  48.  
  49.  
  50.  
  51. /*******************************************************************************
  52.  * Search_BTree
  53.  *
  54.  *******************************************************************************/
  55.  
  56. data_iType Search_BTree(Key_Type key)
  57. {
  58.     if (key != b_cache.key)
  59.     {
  60.         b_cache.key = key;
  61.         b_cache.dIndex = Search1_BTree(header.bRoot, &key);
  62.     }
  63.     return b_cache.dIndex;
  64. } // Search_BTree
  65.  
  66.  
  67.  
  68. /*******************************************************************************
  69.  * Valid_Key
  70.  *
  71.  *******************************************************************************/
  72.  
  73. pascal Boolean Valid_Key(Key_Type *key)
  74. {
  75.     return (Search1_BTree(header.bRoot, key) != NIL);
  76. } // Valid_Key
  77.  
  78.  
  79.  
  80. /*******************************************************************************
  81.  * Max1_Key
  82.  *
  83.  *******************************************************************************/
  84.  
  85. Key_Type Max1_Key(bnode_iType root1)
  86. {
  87.     bRecType        bRec;
  88.     
  89.     Read_bRec(root1, &bRec);
  90.     if (bRec.child[bRec.keyCount] == NIL)
  91.         return (bRec.key[bRec.keyCount - 1]);
  92.     else
  93.         return (Max1_Key(bRec.child[bRec.keyCount]));
  94. } // Max1_Key
  95.  
  96.  
  97.  
  98. /*******************************************************************************
  99.  * Max_Key
  100.  *
  101.  *******************************************************************************/
  102.  
  103. pascal Key_Type Max_Key(void)
  104. {
  105.     if (header.bRoot == NIL)
  106.         return (nokey);
  107.     else
  108.         return (Max1_Key(header.bRoot));
  109. } // Max_Key
  110.  
  111.  
  112.  
  113. /*******************************************************************************
  114.  * Unique1_Key
  115.  *
  116.  *******************************************************************************/
  117.  
  118. Key_Type Unique1_Key(bnode_iType root1, Key_Type *prevKey)
  119. {
  120.     bRecType        bRec;
  121.     short            loop;
  122.     Key_Type        result;
  123.     
  124.     if (root1 == NIL)
  125.         return (nokey);
  126.     else
  127.     {
  128.         Read_bRec(root1, &bRec);
  129.         loop = 0;
  130.         while (loop < bRec.keyCount)
  131.         {
  132.             result = Unique1_Key(bRec.child[loop], prevKey);
  133.             if (result != nokey)
  134.                 return (result);
  135.             if (*prevKey == nokey)
  136.                 *prevKey = bRec.key[loop];
  137.             if (bRec.key[loop] - *prevKey > 1L)
  138.             {
  139.                 result = *prevKey + 1L;
  140.                 return (result);
  141.             }
  142.             *prevKey = bRec.key[loop];
  143.             loop++;
  144.         }
  145.         return (Unique1_Key(bRec.child[loop], prevKey));
  146.     }
  147. } // Unique1_Key
  148.  
  149.  
  150.  
  151. /*******************************************************************************
  152.  * Unique_Key
  153.  *
  154.  *******************************************************************************/
  155.  
  156. pascal Key_Type Unique_Key(void)
  157. {
  158.     Key_Type        prevKey;
  159.     Key_Type        result;
  160.     
  161.     if (header.bRoot == NIL)
  162.         return (nokey);
  163.     else
  164.     {
  165.         prevKey = nokey;
  166.         result = Unique1_Key(header.bRoot, &prevKey);
  167.         if (result == nokey)
  168.             result = prevKey + 1L;
  169.         return (result);
  170.     }
  171. } // Unique_Key
  172.  
  173.  
  174. #ifdef B_TREE_DEBUG
  175.  
  176. #include <string.h>
  177. #include <stdio.h>
  178.  
  179. /*******************************************************************************
  180.  * Tree_Depth
  181.  *
  182.  *******************************************************************************/
  183.  
  184. short Tree_Depth(bnode_iType root1, short depth)
  185. {
  186.     bRecType        bRec;
  187.     
  188.     if (root1 == NIL)
  189.         return depth;
  190.     Read_bRec(root1, &bRec);
  191.     if (bRec.child[bRec.keyCount] == NIL)
  192.         return depth;
  193.     else
  194.         return (Tree*
  195.  * Concatenate
  196.  *
  197.  *******************************************************************************/
  198.  
  199. Boolean Concatenate(bRecType *bRec, short pos)
  200. {
  201.     bRecType        bRec2, bRec3;
  202.     short            loop;
  203.     bnode_iType        concat_rec, eliminate_rec;
  204.     
  205.     Read_bRec(bRec->child[pos], &bRec2);                // the invalid record
  206.     if (pos < bRec->keyCount)
  207.     {                                                    // try right subtree
  208.         concat_rec = bRec->child[pos];
  209.         eliminate_rec = bRec->child[pos + 1];
  210.         Read_bRec(eliminate_rec, &bRec3);                // get key from successor
  211.         Insert_Key(bRec2.key, bRec2.data, bRec2.child, bRec->key[pos], bRec->data[pos], bRec3.child[0], TRUE, bRec2.keyCount, bRec2.keyCount);
  212.         bRec2.keyCount++;
  213.         Delete_Key(bRec->key, bRec->data, bRec->child, pos, bRec->keyCount);
  214.         bRec->keyCount--;
  215.         bRec->child[pos] = concat_rec;
  216.         for(loop = 0; loop < bRec3.keyCount; loop++)    // move keys from right subtree
  217.         {
  218.             Insert_Key(bRec2.key, bRec2.data, bRec2.child, bRec3.key[loop], bRec3.data[loop], bRec3.child[loop + 1], TRUE, bRec2.keyCount, bRec2.keyCount);
  219.             bRec2.keyCount++;
  220.         }
  221.         Dispose_bRec(eliminate_rec);
  222.         Write_bRec(concat_rec, &bRec2);
  223.     }
  224.     else                                                // left subtree
  225.     {
  226.         concat_rec = bRec->child[pos - 1];
  227.         eliminate_rec = bRec->child[pos];
  228.         Read_bRec(concat_rec, &bRec3);                    // get key from successor
  229.         Insert_Key(bRec3.key, bRec3.data, bRec3.child, bRec->key[pos - 1], bRec->data[pos - 1], bRec2.child[0], TRUE, bRec3.keyCount, bRec3.keyCount);
  230.         bRec3.keyCount++;
  231.         Delete_Key(bRec->key, bRec->data, bRec->child, pos - 1, bRec->keyCount);
  232.         bRec->keyCount--;
  233.         bRec->child[pos - 1] = concat_rec;
  234.         for (loop = 0; loop < bRec2.keyCount; loop++)    // move keys from right subtree
  235.         {
  236.             Insert_Key(bRec3.key, bRec3.data, bRec3.child, bRec2.key[loop], bRec2.data[loop], bRec2.child[loop + 1], TRUE, bRec3.keyCount, bRec3.keyCount);
  237.             bRec3.keyCount++;
  238.         }
  239.         Dispose_bRec(eliminate_rec);
  240.         Write_bRec(concat_rec, &bRec3);
  241.     }
  242.  
  243.     return (bRec->keyCount < Minkeys);                    // underflow if true
  244.         
  245. } // Concatenate
  246.  
  247.  
  248.  
  249. /*******************************************************************************
  250.  * Delete1_BTree
  251.  *
  252.  *******************************************************************************/
  253.  
  254. Boolean Delete1_BTree(bnode_iType root1, Key_Type key, data_iType *data)
  255. {
  256.     bRecType        bRec;
  257.     short            pos;
  258.     Key_Type        swap_key;
  259.     Boolean            underflow;
  260.     data_iType        ignore_data;
  261.     Boolean            result;
  262.     
  263.     if (root1 == NIL)
  264.     {                                                    // key not found
  265.         *data = NIL;
  266.         result = FALSE;
  267.     }
  268.     else
  269.     {
  270.         pos = 0;
  271.         Read_bRec(root1, &bRec);
  272.         while ((pos < bRec.keyCount) && (key > bRec.key[pos]))
  273.             pos++;
  274.         if ((pos < bRec.keyCount) && (key == bRec.key[pos]))
  275.         {
  276.             *data = bRec.data[pos];                        // pass back data of deleted key
  277.             if (bRec.child[0] == NIL)
  278.             {                                            // leaf record
  279.                 Delete_Key(bRec.key, bRec.data, bRec.child, pos, bRec.keyCount);
  280.                 bRec.keyCount--;
  281.                 Write_bRec(root1, &bRec);
  282.                 result = (bRec.keyCount < Minkeys);        // underflow if too few keys
  283.                 return (result);
  284.             }
  285.             else                                        // swap internal key with leaf key
  286.             {
  287.                 swap_key = Find_Swap_Key(&bRec, &pos);
  288.                 Write_bRec(root1, &bRec);
  289.                 underflow = Delete1_BTree(bRec.child[pos], swap_key, &ignore_data);
  290.             }
  291.         }
  292.         else                                            // keep searching
  293.             underflow = Delete1_BTree(bRec.child[pos], key, data);
  294.  
  295.         if (underflow)
  296.         {
  297.             if (Redistribute(&bRec, pos) == FALSE)
  298.             {                                            // redistribute worked, no underflow
  299.                 Write_bRec(root1, &bRec);
  300.                 result = FALSE;
  301.             }
  302.             else
  303.             {
  304.                 underflow = Concatenate(&bRec, pos);
  305.                 Write_bRec(root1, &bRec);
  306.                 result = underflow;
  307.             }
  308.         }
  309.         else
  310.             result = FALSE;
  311.     }
  312.     return (result);
  313. } // Delete1_BTree
  314.  
  315.  
  316.  
  317. /*******************************************************************************
  318.  * Delete_BTree
  319.  *
  320.  *******************************************************************************/
  321.  
  322. data_iType Delete_BTree(Key_Type key)
  323. {
  324.     bRecType        bRec;
  325.     data_iType        data;
  326.     
  327.     b_cache.key = nokey;
  328.     b_cache.dIndex = NIL;
  329.  
  330.     if (Delete1_BTree(header.bRoot, key, &data))
  331.     {
  332.         Read_bRec(header.bRoot, &bRec);
  333.         if (bRec.keyCount == 0)
  334.         {
  335.             Dispose_bRec(header.bRoot);
  336.             header.bRoot = bRec.child[0];
  337.             // Write_Header(); called by Dispose_Data
  338.         }
  339.     }
  340.     return (data);
  341. } // Delete_BTree
  342.  
  343.  
  344.  
  345. /*******************************************************************************
  346.  * Read_dRec
  347.  *
  348.  *******************************************************************************/
  349.  
  350. void Read_dRec(data_iType dIndex, dRecType *dRec)
  351. {
  352.     long        size;
  353.     
  354.     err = SetFPos(fileNum, fsFromStart, dIndex);
  355.     size = sizeof(dRecType);
  356.     err = FSRead(fileNum, &size, (Ptr)dRec);
  357. } // Read_dRec
  358.  
  359.  
  360.  
  361. /*******************************************************************************
  362.  * Write_dRec
  363.  *
  364.  *******************************************************************************/
  365.  
  366. void Write_dRec(data_iType dIndex, dRecType *dRec)
  367. {
  368.     long        size;
  369.     
  370.     err = SetFPos(fileNum, fsFromStart, dIndex);
  371.     size = sizeof(dRecType);
  372.     err = FSWrite(fileNum, &size, (Ptr)dRec);
  373. } // Write_dRec
  374.  
  375.  
  376.  
  377. /*******************************************************************************
  378.  * Concat_Free_dRec
  379.  *
  380.  *******************************************************************************/
  381.  
  382. void Concat_Free_dRec(data_iType dIndex, dRecType *dRec)    // dRec must already be made first in free list
  383. {
  384.     dRecType        dRec2, dRec3;
  385.     long            size;
  386.     
  387.     size = sizeof(dRecType) + abs(dRec->pLength);
  388.     if (((dIndex + size) / dBlockSize) == (dIndex / dBlockSize))    // next dRec must be in same block
  389.     {
  390.         Read_dRec(dIndex + size, &dRec2);
  391.         if (dRec2.pLength < 0)
  392.         {                                                    // adjacent dRec is free, combine it
  393.             if (dRec2.parm.back == dIndex)
  394.                 dRec->next = dRec2.next;                    // adjacent dRec is also next in free list
  395.             else if (dRec2.parm.back != NIL)                // this should never be NIL
  396.             {                                                // update next free record
  397.                 Read_dRec(dRec2.parm.back, &dRec3);
  398.                 dRec3.next = dRec2.next;
  399.                 Write_dRec(dRec2.parm.back, &dRec3);
  400.             }
  401.  
  402.             if (dRec2.next != NIL)
  403.             {                                                // update previous free record
  404.                 Read_dRec(dRec2.next, &dRec3);
  405.                 dRec3.parm.back = dRec2.parm.back;
  406.                 Write_dRec(dRec2.next, &dRec3);
  407.             }
  408.             dRec->pLength = -1 * (size + abs(dRec2.pLength));
  409.             Concat_Free_dRec(dIndex, dRec);
  410.         }
  411.     }
  412. } // Concat_Free_dRec
  413.  
  414.  
  415.  
  416. /*******************************************************************************
  417.  * Free_dRec
  418.  *
  419.  *******************************************************************************/
  420.  
  421. void Free_dRec(data_iType dIndex, dRecType *dRec)
  422. {
  423.      dRecType        dRec2;
  424.      
  425.     if (header.free_dList != NIL)
  426.     {
  427.         Read_dRec(header.free_dList, &dRec2);
  428.         dRec2.parm.back = dIndex;
  429.         Write_dRec(header.free_dList, &dRec2);
  430.     }
  431.     dRec->pLength = -1 * abs(dRec->pLength);    // free dRec has negative length
  432.     dRec->next = header.free_dList;
  433.     dRec->parm.back = NIL;
  434.     header.free_dList = dIndex;
  435.     Concat_Free_dRec(dIndex, dRec);
  436.     Write_dRec(dIndex, dRec);
  437. } // Free_dRec
  438.  
  439.  
  440.  
  441. /*******************************************************************************
  442.  * Grow_dList
  443.  *
  444.  *******************************************************************************/
  445.  
  446. data_iType Grow_dList(void)
  447. {
  448.     long        startEOF, curEOF;
  449.     dRecType    dRec;
  450.     
  451.     err = GetEOF(fileNum, &startEOF);
  452.     Write_BlockId(dBlockId);
  453.     curEOF = startEOF + sizeof(block_idType);
  454.     dRec.pLength = dBlockSize - sizeof(block_idType) - sizeof(dRecType); // create new dRec
  455.     Write_dRec(curEOF, &dRec);
  456.     err = SetEOF(fileNum, startEOF + dBlockSize);
  457.     Free_dRec(curEOF, &dRec);                // add dRec to header.free_dList
  458.     if (err == noErr)
  459.         return (curEOF);
  460.     else
  461.         return (NIL);
  462. } // Grow_dList
  463.  
  464.  
  465.  
  466. /*******************************************************************************
  467.  * New_dRec
  468.  *
  469.  *******************************************************************************/
  470.  
  471. data_iType New_dRec(dRecType *dRec)
  472. {
  473.     dRecType        dRec2;
  474.     data_iType        dIndex;
  475.     
  476.     if (header.free_dList == NIL)
  477.         header.free_dList = Grow_dList();
  478.     Read_dRec(header.free_dList, dRec);
  479.     Concat_Free_dRec(header.free_dList, dRec);
  480.     dIndex = header.free_dList;
  481.     header.free_dList = dRec->next;
  482.     if (header.free_dList != NIL)
  483.     {
  484.         Read_dRec(header.free_dList, &dRec2);
  485.         dRec2.parm.back = NIL;
  486.         Write_dRec(header.free_dList, &dRec2);
  487.     }
  488.     dRec->pLength = abs(dRec->pLength);        // block is now in use
  489.     dRec->next = NIL;
  490.     dRec->parm.timestamp = 0L;
  491.     dRec->parent = nokey;
  492.     dRec->children = NIL;
  493.     Write_dRec(dIndex, dRec);                // so concat_free_drec doesn't think it's still free
  494.     return (dIndex);
  495. } // New_dRec
  496.  
  497.  
  498.  
  499. /*******************************************************************************
  500.  * Read_TimeStamp
  501.  *
  502.  *******************************************************************************/
  503.  
  504. pascal TimeStamp_Type Read_TimeStamp(Key_Type key)
  505. {
  506.     data_iType        dIndex;
  507.     dRecType        dRec;
  508.     
  509.     err = noErr;
  510.     dIndex = Search_BTree(key);
  511.     if (dIndex != NIL)
  512.     {
  513.         Read_dRec(dIndex, &dRec);
  514.         return (dRec.parm.timestamp);
  515.     }
  516.     return 0L;
  517. } // Read_TimeStamp
  518.  
  519.  
  520.  
  521. /*******************************************************************************
  522.  * Get1_Children
  523.  *
  524.  *******************************************************************************/
  525.  
  526. Handle Get1_Children(data_iType dIndex)
  527. {
  528.     Handle        children;
  529.     
  530.     if (dIndex != NIL)
  531.     {
  532.         children = Read1_Data(dIndex, NULL);
  533.         if (err != noErr)
  534.             return NULL;
  535.             
  536.         return children;
  537.     }
  538.     return NULL;
  539. } // Get1_Children
  540.  
  541.  
  542.  
  543. /*******************************************************************************
  544.  * Get_Children
  545.  *
  546.  *******************************************************************************/
  547.  
  548. pascal Handle Get_Children(Key_Type key)
  549. {
  550.     data_iType            dIndex;
  551.     dRecType            dRec;
  552.  
  553.     err = noErr;
  554.     
  555.     dIndex = Search_BTree(key);
  556.     if (dIndex != NIL)
  557.     {
  558.         Read_dRec(dIndex, &dRec);
  559.         
  560.         return Get1_Children(dRec.children);
  561.     }
  562.     return NULL;
  563. } // Get_Children
  564.  
  565.  
  566.  
  567. /*******************************************************************************
  568.  * Has_Children
  569.  *
  570.  *******************************************************************************/
  571.  
  572. pascal Boolean Has_Children(Key_Type key)
  573. {
  574.     data_iType            dIndex;
  575.     dRecType            dRec;
  576.  
  577.     err = noErr;
  578.     
  579.     dIndex = Search_BTree(key);
  580.     if (dIndex != NIL)
  581.     {
  582.         Read_dRec(dIndex, &dRec);
  583.         
  584.         return (dRec.children != NIL);
  585.     }
  586.     return FALSE;
  587. } // Has_Children
  588.  
  589.  
  590.  
  591. /*******************************************************************************
  592.  * Get_Parent
  593.  *
  594.  *******************************************************************************/
  595.  
  596. pascal Key_Type Get_Parent(Key_Type key)
  597. {
  598.     data_iType            dIndex;
  599.     dRecType            dRec;
  600.  
  601.     err = noErr;
  602.     
  603.     dIndex = Search_BTree(key);
  604.     if (dIndex != NIL)
  605.     {
  606.         Read_dRec(dIndex, &dRec);
  607.         
  608.         return (dRec.parent);
  609.     }
  610.     return FALSE;
  611. } // Get_Parent
  612.  
  613.  
  614.  
  615. /*******************************************************************************
  616.  * Remove1_Parent_From_Child
  617.  *
  618.  *******************************************************************************/
  619.  
  620. Boolean Remove1_Parent_From_Child(Key_Type key)
  621. {
  622.     data_iType            dIndex, dIndex2;
  623.     dRecType            dRec, dRec2;
  624.     Handle                children;
  625.     SubRec_Element_Type    *child;
  626.     short                child_index;
  627.  
  628.     dIndex = Search_BTree(key);
  629.     if (dIndex != NIL)
  630.     {
  631.         Read_dRec(dIndex, &dRec);
  632.  
  633.         if (dRec.parent != nokey)
  634.         {
  635.             dIndex2 = Search_BTree(dRec.parent);
  636.             if (dIndex2 == NIL)
  637.             {
  638.                 err = SubRecIntegrityError;
  639.                 return FALSE;
  640.             }
  641.             
  642.             Read_dRec(dIndex2, &dRec2);
  643.             
  644.             children = Get1_Children(dRec2.children);
  645.             if (children == NULL)
  646.             {
  647.                 err = SubRecIntegrityError;
  648.                 return FALSE;
  649.             }
  650.             
  651.             // find element relating parent to child and remove it
  652.             HLock(children);
  653.             child_index = 0;
  654.             child = (SubRec_Element_Type *)((long)(*children) + sizeof(short));
  655.             while (child_index < *((short *)(*children)))
  656.             {
  657.                 if (key == child[child_index].id)
  658.                 {
  659.                     // delete relative record element
  660.                     BlockMove((Ptr)&(child[child_index + 1]), (Ptr)&(child[child_index]), (*((short *)(*children)) - child_index - 1) * sizeof(SubRec_Element_Type));
  661.                     (*((short *)(*children)))--;
  662.                     HUnlock(children);
  663.                     SetHandleSize(children, GetHandleSize(children) - sizeof(SubRec_Element_Type));
  664.                     // SetHandleSize should never fail here because children gets smaller
  665.                     HLock(children);
  666.                     
  667.                     // re-save or remove children record
  668.                     Remember_Relatives(NIL);
  669.                     Dispose1_Data(dRec2.children);
  670.                     if (*((short *)(*children)) > 0)
  671.                         dRec2.children = Save1_Data(*children, GetHandleSize(children));
  672.                     else
  673.                         dRec2.children = NIL;
  674.                     Write_dRec(dIndex2, &dRec2);
  675.                     
  676.                     HUnlock(children);
  677.                     DisposHandle(children);
  678.  
  679.                     // remove reference to parent from child
  680.                     dRec.parent = nokey;
  681.                     Write_dRec(dIndex, &dRec);
  682.                     
  683.                     Write_Header(); // also called by Dispose_Data
  684.                     return TRUE;
  685.                 }
  686.                 child_index++;
  687.             }
  688.             err = SubRecIntegrityError;
  689.         }
  690.     }
  691.     return FALSE;
  692. } // Remove1_Parent_From_Child
  693.  
  694.  
  695.  
  696. /*******************************************************************************
  697.  * Remove_Parent_From_Child
  698.  *
  699.  *******************************************************************************/
  700.  
  701. pascal void Remove_Parent_From_Child(Key_Type key)
  702. {
  703.     err = noErr;
  704.     
  705.     if (Remove1_Parent_From_Child(key))
  706.         Write_Header();
  707. } // Remove_Parent_From_Child
  708.  
  709.  
  710.  
  711. /*******************************************************************************
  712.  * Dispose1_Children
  713.  *
  714.  *******************************************************************************/
  715.  
  716. Boolean Dispose1_Children(Key_Type key)
  717. {
  718.     data_iType            dIndex;
  719.     dRecType            dRec;
  720.     Handle                children;
  721.     SubRec_Element_Type    *child;
  722.     short                child_index;
  723.  
  724.     dIndex = Search_BTree(key);
  725.     if (dIndex != NIL)
  726.     {
  727.         Read_dRec(dIndex, &dRec);
  728.  
  729.         if (dRec.children != NIL)
  730.         {
  731.             children = Get1_Children(dRec.children);
  732.             if (children == NULL)
  733.             {
  734.                 err = SubRecIntegrityError;
  735.                 return FALSE;
  736.             }
  737.             
  738.             // dispose of children record
  739.             Dispose1_Data(dRec.children);
  740.  
  741.             // remove reference to children from parent
  742.             dRec.children = NIL;
  743.             Write_dRec(dIndex, &dRec);
  744.  
  745.             HLock(children);
  746.             child_index = 0;
  747.             child = (SubRec_Element_Type *)((long)(*children) + sizeof(short));
  748.     
  749.             // dispose of all children records
  750.             while (child_index < *((short *)(*children)))
  751.             {
  752.                 Dispose1_Children(child[child_index].id);    // dispose of children's children
  753.                 Dispose1_Data(Delete_BTree(child[child_index].id));    // dispose of index to data and data
  754.                 child_index++;
  755.             }
  756.             HUnlock(children);
  757.             DisposHandle(children);
  758.             
  759.             return TRUE;
  760.         }
  761.     }
  762.     return FALSE;
  763. } // Dispose1_Children
  764.  
  765.  
  766.  
  767. /*******************************************************************************
  768.  * Dispose_Children
  769.  *
  770.  *******************************************************************************/
  771.  
  772. pascal void Dispose_Children(Key_Type key)
  773. {
  774.     err = noErr;
  775.     
  776.     if (Dispose1_Children(key))
  777.         Write_Header();
  778. } // Dispose_Children
  779.  
  780.  
  781.  
  782. /*******************************************************************************
  783.  * Relate
  784.  *
  785.  *******************************************************************************/
  786.  
  787. pascal Boolean Relate(Key_Type parent_id, Key_Type child_id, User_Data user_data, short before)
  788. {
  789.     data_iType            dIndex, dIndex2;
  790.     dRecType            dRec, dRec2;
  791.     Handle                children;
  792.     SubRec_Element_Type    *child;
  793.     short                child_index;
  794.  
  795.     err = noErr;
  796.     
  797.     dIndex = Search_BTree(parent_id);
  798.     if (dIndex != NIL)
  799.     {
  800.         dIndex2 = Search_BTree(child_id);
  801.         if (dIndex2 != NIL)
  802.         {
  803.             Read_dRec(dIndex, &dRec);
  804.             
  805.             if (dRec.children == NIL)
  806.             {
  807.                 // first child
  808.                 children = NewHandle(sizeof(short));
  809.                 err = MemError();
  810.                 if (err != noErr)
  811.                     return FALSE;
  812.                 *((short *)(*children)) = 0;
  813.             }
  814.             else
  815.             {
  816.                 children = Get1_Children(dRec.children);
  817.                 if (children == NULL)
  818.                 {
  819.                     err = SubRecIntegrityError;
  820.                     return FALSE;
  821.                 }
  822.             }
  823.             
  824.             HLock(children);
  825.             child_index = 0;
  826.             child = (SubRec_Element_Type *)((long)(*children) + sizeof(short));
  827.     
  828.             // is this child already a child of this parent record?
  829.             while (child_index < *((short *)(*children)))
  830.             {
  831.                 if (child_id == child[child_index].id)
  832.                 {
  833.                     if (before != child_index)
  834.                     {
  835.                         // shift elements so available element is last element
  836.                         BlockMove((Ptr)&(child[child_index + 1]), (Ptr)&(child[child_index]), (*((short *)(*children)) - child_index - 1) * sizeof(SubRec_Element_Type));
  837.                     }
  838.                     break;
  839.                 }
  840.                 child_index++;
  841.             }
  842.             
  843.             if (child_index == *((short *)(*children)))
  844.             {
  845.                 // add new child element
  846.                 HUnlock(children);
  847.                 SetHandleSize(children, GetHandleSize(children) + sizeof(SubRec_Element_Type));
  848.                 err = MemError();
  849.                 if (err != noErr)
  850.                     return FALSE;
  851.                 HLock(children);
  852.                 (*((short *)(*children)))++;
  853.                 child = (SubRec_Element_Type *)((long)(*children) + sizeof(short));
  854.             }
  855.             
  856.             // insert at end of list?
  857.             if ((before < 0) || (before >= *((short *)(*children))))
  858.                 before = *((short *)(*children)) - 1;
  859.             
  860.             // shift elements so available element is at the "before" position
  861.             if (before != child_index)
  862.                 BlockMove((Ptr)&(child[before]), (Ptr)&(child[before + 1]), (*((short *)(*children)) - before - 1) * sizeof(SubRec_Element_Type));
  863.     
  864.             // copy information to child element for this parent
  865.             child[before].id = child_id;
  866.             BlockMove((Ptr)user_data, (Ptr)(child[before].user_data), sizeof(User_Data));
  867.     
  868.             // re-save children record
  869.             Remember_Relatives(NIL);
  870.             Dispose1_Data(dRec.children);
  871.             dRec.children = Save1_Data(*children, GetHandleSize(children));
  872.             Write_dRec(dIndex, &dRec);
  873.  
  874.             HUnlock(children);
  875.             DisposHandle(children);
  876.             
  877.             // update reference to parent in child
  878.             Read_dRec(dIndex2, &dRec2);
  879.             dRec2.parent = parent_id;
  880.             Write_dRec(dIndex2, &dRec2);
  881.             
  882.             Write_Header();
  883.             return TRUE;
  884.         }
  885.     }
  886.     return FALSE;
  887. } // Relate
  888.  
  889.  
  890.  
  891. /*******************************************************************************
  892.  * Remember_Relatives
  893.  *
  894.  *******************************************************************************/
  895.  
  896. void Remember_Relatives(data_iType dIndex)
  897. {
  898.     dRecType            dRec;
  899.  
  900.     if (dIndex != NIL)
  901.     {
  902.         Read_dRec(dIndex, &dRec);
  903.         remember_parent = dRec.parent;
  904.         remember_children = dRec.children;
  905.     }
  906.     else
  907.     {
  908.         remember_parent = nokey;
  909.         remember_children = NIL;
  910.     }
  911. } // Remember_Relatives
  912.  
  913.  
  914.  
  915. /*******************************************************************************
  916.  * Restore_Relatives
  917.  *
  918.  *******************************************************************************/
  919.  
  920. void Restore_Relatives(dRecType *dRec)
  921. {
  922.     dRec->parent = remember_parent;
  923.     dRec->children = remember_children;
  924. } // Restore_Relatives
  925.  
  926.  
  927.  
  928. /*******************************************************************************
  929.  * Dispose1_Data
  930.  *
  931.  *******************************************************************************/
  932.  
  933. void Dispose1_Data(data_iType dIndex)        // dispose of data but not index to data
  934. {
  935.     dRecType        dRec;
  936.     
  937.     if (dIndex != NIL)
  938.     {
  939.         Read_dRec(dIndex, &dRec);
  940.         Dispose1_Data(dRec.next);
  941.         Free_dRec(dIndex, &dRec);
  942.     }
  943. } // Dispose1_Data
  944.  
  945.  
  946.  
  947. /*******************************************************************************
  948.  * Dispose_Data
  949.  *
  950.  *******************************************************************************/
  951.  
  952. pascal Boolean Dispose_Data(Key_Type key, TimeStamp_Type *old_timestamp)
  953. {
  954.     TimeStamp_Type    timestamp;
  955.     
  956.     err = noErr;
  957.     
  958.     if (old_timestamp)
  959.     {
  960.         timestamp = Read_TimeStamp(key);
  961.         if ((*old_timestamp) && (timestamp != *old_timestamp))
  962.         {
  963.             *old_timestamp = timestamp;
  964.             err = TimeStampError;
  965.             return (FALSE);
  966.         }
  967.         *old_timestamp = timestamp;
  968.     }
  969.     
  970.     Remove1_Parent_From_Child(key);
  971.     Dispose1_Children(key);
  972.  
  973.     Dispose1_Data(Delete_BTree(key));    // dispose of index to data and data
  974.     Write_Header();
  975.     
  976.     return (err == noErr);
  977. } // Dispose_Data
  978.  
  979.  
  980.  
  981. /*******************************************************************************
  982.  * Save1_Data
  983.  *
  984.  *******************************************************************************/
  985.  
  986. data_iType Save1_Data(Ptr data, short dataLen)
  987. {
  988.     dRecType        dRec, dRec2;
  989.     data_iType        dIndex;
  990.     long            size;
  991.     data_iType        result;
  992.     
  993.     dIndex = New_dRec(&dRec);
  994.     if (dataLen >= dRec.pLength)
  995.         size = dRec.pLength;                        // fragment large data
  996.     else
  997.         size = dataLen;                                // fragment record into used & free parts
  998.         
  999.     err = SetFPos(fileNum, fsFromStart, dIndex + sizeof(dRecType));
  1000.     err = FSWrite(fileNum, &size, data);
  1001.  
  1002.     if (dRec.pLength - size > sizeof(dRecType))
  1003.     {                                                // make unused portion of data record free
  1004.         dRec2.pLength = dRec.pLength - size - sizeof(dRecType);
  1005.         Free_dRec(dIndex + sizeof(dRecType) + size, &dRec2);
  1006.         dRec.pLength = size;
  1007.     }
  1008.         
  1009.     if (dataLen > size)
  1010.         dRec.next = Save1_Data((Ptr)((long)data + size), dataLen - size);    // fragment data
  1011.     else
  1012.         dRec.next = NIL;                            // end of data
  1013.     dRec.aLength = size;
  1014.     GetDateTime(&(dRec.parm.timestamp));
  1015.     Restore_Relatives(&dRec);
  1016.     Write_dRec(dIndex, &dRec);
  1017.     return (dIndex);
  1018. } // Save1_Data
  1019.  
  1020.  
  1021.  
  1022. /*******************************************************************************
  1023.  * Save_Data
  1024.  *
  1025.  *******************************************************************************/
  1026.  
  1027. pascal Boolean Save_Data(Key_Type key, Handle data, TimeStamp_Type *old_timestamp)
  1028. {
  1029.     data_iType        dIndex;
  1030.     dRecType        dRec;
  1031.     TimeStamp_Type    timestamp;
  1032.     
  1033.     if (GetHandleSize(data) > 0L)
  1034.     {
  1035.         err = noErr;
  1036.         dIndex = Search_BTree(key);
  1037.         Remember_Relatives(dIndex);
  1038.         if (dIndex != NIL)
  1039.         {
  1040.             if (old_timestamp)
  1041.             {
  1042.                 Read_dRec(dIndex, &dRec);
  1043.                 timestamp = dRec.parm.timestamp;
  1044.                 if ((*old_timestamp) && (timestamp != *old_timestamp))
  1045.                 {
  1046.                     *old_timestamp = timestamp;
  1047.                     err = TimeStampError;
  1048.                     return (FALSE);
  1049.                 }
  1050.                 *old_timestamp = timestamp;
  1051.             }
  1052.             Dispose1_Data(dIndex);            // dispose of existing data
  1053.         }
  1054.         
  1055.         HLock(data);
  1056.         Insert_BTree(key, dIndex = Save1_Data(*data, GetHandleSize(data))); // insert data & update index's data
  1057.         HUnlock(data);
  1058.         Write_Header();
  1059.         if ((old_timestamp) && (err == noErr))
  1060.         {
  1061.             Read_dRec(dIndex, &dRec);
  1062.             *old_timestamp = dRec.parm.timestamp;
  1063.         }
  1064.         return (err == noErr);
  1065.     }
  1066.     else
  1067.         return (Dispose_Data(key, old_timestamp));    // dispose of existing data & index when new data is empty
  1068. } // Save_Data
  1069.  
  1070.  
  1071.  
  1072. /*******************************************************************************
  1073.  * Read1_Data
  1074.  *
  1075.  *******************************************************************************/
  1076.  
  1077. Handle Read1_Data(data_iType dIndex, TimeStamp_Type *timestamp)
  1078. {
  1079.     dRecType        dRec;
  1080.     Handle            data = NULL;
  1081.     long            size, pos;
  1082.     
  1083.     if (dIndex != NIL)
  1084.     {
  1085.         do {
  1086.             Read_dRec(dIndex, &dRec);
  1087.             if (data == NULL)
  1088.             {                                        // make space for first fragment of data
  1089.                 if (timestamp)
  1090.                     *timestamp = dRec.parm.timestamp;
  1091.                 pos = 0L;
  1092.                 data = NewHandle(dRec.aLength);
  1093.                 err = MemError();
  1094.                 if (err != noErr)
  1095.                     return (NULL);
  1096.             }
  1097.             else                                    // make space for additional data fragments
  1098.             {
  1099.                 pos = GetHandleSize(data);
  1100.                 SetHandleSize(data, pos + dRec.aLength);
  1101.                 err = MemError();
  1102.                 if (err != noErr)
  1103.                     return (NULL);
  1104.             }
  1105.             err = SetFPos(fileNum, fsFromStart, dIndex + sizeof(dRecType));
  1106.             size = dRec.aLength;
  1107.             HLock(data);
  1108.             err = FSRead(fileNum, &size, (Ptr)((long)(*data) + pos));
  1109.             HUnlock(data);
  1110.             dIndex = dRec.next;
  1111.         } while (dIndex != NIL);
  1112.     }
  1113.     return (data);
  1114. } // Read1_Data
  1115.  
  1116.  
  1117.  
  1118. /*******************************************************************************
  1119.  * Read_Data
  1120.  *
  1121.  *******************************************************************************/
  1122.  
  1123. pascal Handle Read_Data(Key_Type key, TimeStamp_Type *timestamp)
  1124. {
  1125.     err = noErr;
  1126.     return Read1_Data(Search_BTree(key), timestamp);
  1127. } // Read_Data
  1128.  
  1129.  
  1130.  
  1131. /*******************************************************************************
  1132.  * Compare_Strs
  1133.  *
  1134.  *******************************************************************************/
  1135.  
  1136. short Compare_Strs(unsigned char *str1, unsigned char *str2, short len1, short len2)
  1137. {
  1138.     short            loop = 0;
  1139.     short            shorter = (len1 > len2 ? len2 : len1);
  1140.     unsigned char    c1, c2;
  1141.     
  1142.     while (loop < shorter)
  1143.     {
  1144.         c1 = str1[loop];
  1145.         c2 = str2[loop];
  1146.         #if !indexCaseSensitive
  1147.         if ((c1 >= 0x61) && (c1 <= 0x7A)) c1 -= 0x20;    // case in-sensitive
  1148.         if ((c2 >= 0x61) && (c2 <= 0x7A)) c2 -= 0x20;    // case in-sensitive
  1149.         #endif
  1150.         if (c1 > c2)
  1151.             return 1;                                    // str1 > str2
  1152.         else if (c1 < c2)
  1153.             return -1;                                    // str1 < str2
  1154.         loop++;
  1155.     }
  1156.  
  1157.     if (len1 > len2)
  1158.         return 1;                                        // str1 > str2
  1159.     else if (len1 < len2)
  1160.         return -1;                                        // str1 < str2
  1161.     else
  1162.         return 0;                                        // str1 == str2
  1163. } // Compare_Strs
  1164.  
  1165.  
  1166.  
  1167. /*******************************************************************************
  1168.  * Init_iRec
  1169.  *
  1170.  *******************************************************************************/
  1171.  
  1172. void Init_iRec(iRecType *iRec)
  1173. {
  1174.     iRec->next = NIL;
  1175.     iRec->previous = NIL;
  1176.     iRec->index[0] = '\0';
  1177.     iRec->id = NoID;
  1178. } // Init_iRec
  1179.  
  1180.  
  1181.  
  1182. /*******************************************************************************
  1183.  * Read_iRec
  1184.  *
  1185.  *******************************************************************************/
  1186.  
  1187. void Read_iRec(long elem, iRecType *iRec)
  1188. {
  1189.     long        size;
  1190.     
  1191.     err = SetFPos(fileNum, fsFromStart, elem);
  1192.     size = sizeof(iRecType);
  1193.     err = FSRead(fileNum, &size, iRec);
  1194. } // Read_iRec
  1195.  
  1196.  
  1197.  
  1198. /*******************************************************************************
  1199.  * Write_iRec
  1200.  *
  1201.  *******************************************************************************/
  1202.  
  1203. void Write_iRec(long elem, iRecType *iRec)
  1204. {
  1205.     long        size;
  1206.     
  1207.     err = SetFPos(fileNum, fsFromStart, elem);
  1208.     size = sizeof(iRecType);
  1209.     err = FSWrite(fileNum, &size, iRec);
  1210. } // Write_iRec
  1211.  
  1212.  
  1213.  
  1214. /*******************************************************************************
  1215.  * Grow_iList
  1216.  *
  1217.  *******************************************************************************/
  1218.  
  1219. long Grow_iList(void)
  1220. {
  1221.     long        startEOF, curEOF;
  1222.     iRecType    iRec;
  1223.     long        size;
  1224.     
  1225.     err = GetEOF(fileNum, &startEOF);
  1226.     Write_BlockId(iBlockId);
  1227.     curEOF = startEOF + sizeof(block_idType);
  1228.     size = sizeof(iRecType);
  1229.     while (((curEOF + size - 1L) / iBlockSize) == (startEOF / iBlockSize))
  1230.     {
  1231.         Init_iRec(&iRec);
  1232.         if (((curEOF + size * 2L - 1L) / iBlockSize) == (startEOF / iBlockSize))
  1233.             iRec.next = curEOF + size;            // link free list
  1234.         Write_iRec(curEOF, &iRec);
  1235.         curEOF += size;
  1236.     }
  1237.     
  1238.     size = iBlockSize - (curEOF % iBlockSize);
  1239.     if (size < iBlockSize)
  1240.         err = SetEOF(fileNum, curEOF + size);
  1241.     if (err == noErr)
  1242.         return (startEOF + sizeof(block_idType));
  1243.     else
  1244.         return (NIL);
  1245. } // Grow_iList
  1246.  
  1247.  
  1248.  
  1249. /*******************************************************************************
  1250.  * New_iRec
  1251.  *
  1252.  *******************************************************************************/
  1253.  
  1254. long New_iRec(iRecType *iRec)
  1255. {
  1256.     long        result;
  1257.     
  1258.     if (header.free_iList == NIL)
  1259.         header.free_iList = Grow_iList();
  1260.     result = header.free_iList;
  1261.     Read_iRec(header.free_iList, iRec);
  1262.     header.free_iList = iRec->next;
  1263.     header.iCount++;
  1264.     Init_iRec(iRec);
  1265.     return (result);
  1266. } // New_iRec
  1267.  
  1268.  
  1269.  
  1270. /*******************************************************************************
  1271.  * Dispose_iRec
  1272.  *
  1273.  *******************************************************************************/
  1274.  
  1275. void Dispose_iRec(long elem)
  1276. {
  1277.     iRecType        iRec;
  1278.     
  1279.     Init_iRec(&iRec);
  1280.     iRec.next = header.free_iList;
  1281.     header.free_iList = elem;
  1282.     header.iCount--;
  1283.     Write_iRec(elem, &iRec);
  1284. } // Dispose_iRec
  1285.  
  1286.  
  1287.  
  1288. /*******************************************************************************
  1289.  * Find_Elem
  1290.  *
  1291.  *******************************************************************************/
  1292.  
  1293. long Find_Elem(ID_Type id)
  1294. {
  1295.     long        elem;
  1296.     iRecType    iRec;
  1297.     
  1298.     elem = ReadiCache(id);
  1299.     if (elem == NIL)
  1300.     {
  1301.         elem = header.iRoot;
  1302.         while (elem != NIL)
  1303.         {
  1304.             Read_iRec(elem, &iRec);
  1305.             if (iRec.id == id)
  1306.                 break;
  1307.             elem = iRec.next;
  1308.         }
  1309.     }
  1310.     return (elem);
  1311. } // Find_Elem
  1312.  
  1313.  
  1314.  
  1315. /*******************************************************************************
  1316.  * Read_Index
  1317.  *
  1318.  *******************************************************************************/
  1319.  
  1320. pascal ID_Type Read_Index(ID_Type id)
  1321. {
  1322.     long        elem;
  1323.     iRecType    iRec;
  1324.  
  1325.     err = noErr;
  1326.     if (id == NoID)
  1327.     {                                    // return id of first element
  1328.         if (header.iRoot == NIL)
  1329.             return (NoID);
  1330.         Read_iRec(header.iRoot, &iRec);
  1331.         WriteiCache(iRec.id, header.iRoot);
  1332.         return (iRec.id);
  1333.     }
  1334.     else
  1335.     {                                    // verify id of this element}
  1336.         elem = Find_Elem(id);
  1337.         if (elem == NIL)
  1338.             return (NoID);
  1339.         else
  1340.         {
  1341.             Read_iRec(elem, &iRec);
  1342.             WriteiCache(id, elem);
  1343.             return (id);
  1344.         }
  1345.     }
  1346. } // Read_Index
  1347.  
  1348.  
  1349.  
  1350. /*******************************************************************************
  1351.  * Read_Next
  1352.  *
  1353.  *******************************************************************************/
  1354.  
  1355. pascal ID_Type Read_Next(ID_Type current_id)
  1356. {
  1357.     long        elem;
  1358.     iRecType    iRec;
  1359.  
  1360.     err = noErr;
  1361.     if (current_id == NoID)
  1362.     {                                        // return id of first element
  1363.         if (header.iRoot == NIL)
  1364.             return (NoID);
  1365.         Read_iRec(header.iRoot, &iRec);
  1366.         WriteiCache(iRec.id, header.iRoot);
  1367.         return (iRec.id);
  1368.     }
  1369.     else
  1370.     {                                        // return id of next element
  1371.         elem = Find_Elem(current_id);
  1372.         if (elem == NIL)
  1373.             return (NoID);
  1374.         else
  1375.         {
  1376.             Read_iRec(elem, &iRec);
  1377.             elem = iRec.next;
  1378.             if (elem == NIL)
  1379.                 return (NoID);
  1380.             else
  1381.             {
  1382.                 Read_iRec(elem, &iRec);
  1383.                 WriteiCache(iRec.id, elem);
  1384.                 return (iRec.id);
  1385.             }
  1386.         }
  1387.     }
  1388. } // Read_Next
  1389.  
  1390.  
  1391.  
  1392. /*******************************************************************************
  1393.  * Read_Previous
  1394.  *
  1395.  *******************************************************************************/
  1396.  
  1397. pascal ID_Type Read_Previous(ID_Type current_id)
  1398. {
  1399.     long        elem;
  1400.     iRecType    iRec;
  1401.  
  1402.     err = noErr;
  1403.     if (current_id == NoID)
  1404.     {                                            // return id of last element
  1405.         if (header.iRoot == NIL)
  1406.             return (NoID);
  1407.         elem = header.iRoot;
  1408.         while (elem != NIL)
  1409.         {
  1410.             Read_iRec(elem, &iRec);
  1411.             elem = iRec.next;
  1412.         }
  1413.         return (iRec.id);
  1414.     }
  1415.     else
  1416.     {                                            // return id of previous element
  1417.         elem = Find_Elem(current_id);
  1418.         if (elem == NIL)
  1419.             return (NoID);
  1420.         else
  1421.         {
  1422.             Read_iRec(elem, &iRec);
  1423.             elem = iRec.previous;
  1424.             if (elem == NIL)
  1425.                 return (NoID);
  1426.             else
  1427.             {
  1428.                 Read_iRec(elem, &iRec);
  1429.                 WriteiCache(iRec.id, elem);
  1430.                 return (iRec.id);
  1431.             }
  1432.         }
  1433.     }
  1434. } // Read_Previous
  1435.  
  1436.  
  1437.  
  1438. /*******************************************************************************
  1439.  * Insert_Index
  1440.  *
  1441.  *******************************************************************************/
  1442.  
  1443. pascal void Insert_Index(Index_Type index, ID_Type id)
  1444. {
  1445.     iRecType        newRec;
  1446.     iRecType        iRec;
  1447.     long            newElem;
  1448.     long            elem;
  1449.     
  1450.     err = noErr;
  1451.  
  1452.     newElem = New_iRec(&newRec);
  1453.     BlockMove((Ptr)index, (Ptr)(newRec.index), (long)(index[0] + 1));
  1454.     newRec.id = id;
  1455.  
  1456.     if (header.iRoot == NIL)
  1457.         header.iRoot = newElem;
  1458.     else
  1459.     {
  1460.         elem = header.iRoot;
  1461.         Read_iRec(elem, &iRec);
  1462.  
  1463.         // special case, first element in list
  1464.         if (Compare_Strs(&(index[1]), &(iRec.index[1]), index[0], iRec.index[0]) == -1)
  1465.         {
  1466.             newRec.next = elem;
  1467.             newRec.previous = NIL;
  1468.             iRec.previous = newElem;
  1469.             Write_iRec(elem, &iRec);
  1470.             header.iRoot = newElem;
  1471.         }
  1472.         else
  1473.         {
  1474.             // search until iRec is the element which comes after our new element
  1475.             while (Compare_Strs(&(index[1]), &(iRec.index[1]), index[0], iRec.index[0]) != -1)
  1476.             {
  1477.                 if (iRec.next == NIL)
  1478.                 {
  1479.                     // insert at the end of the list, create dummy iRec that follows our new element
  1480.                     iRec.next = NIL;
  1481.                     iRec.previous = elem;
  1482.                     elem = NIL;
  1483.                     break;
  1484.                 }
  1485.                 elem = iRec.next;
  1486.                 Read_iRec(elem, &iRec);
  1487.             }
  1488.  
  1489.             // insert in middle of list, iRec is the element after our new element
  1490.             newRec.previous = iRec.previous;
  1491.             newRec.next = elem;
  1492.             iRec.previous = newElem;
  1493.             if (elem != NIL)
  1494.                 Write_iRec(elem, &iRec);
  1495.                 
  1496.             // read and update the element before our new element
  1497.             Read_iRec(newRec.previous, &iRec);
  1498.             iRec.next = newElem;
  1499.             Write_iRec(newRec.previous, &iRec);
  1500.         }
  1501.  
  1502.     } // if header.iRoot == NIL
  1503.  
  1504.     Write_iRec(newElem, &newRec);
  1505.     Write_Header();
  1506. } // Insert_Index
  1507.  
  1508.  
  1509.  
  1510. /*******************************************************************************
  1511.  * Delete_Index
  1512.  *
  1513.  *******************************************************************************/
  1514.  
  1515. pascal void Delete_Index(ID_Type id)
  1516. {
  1517.     iRecType        iRec, iRec2;
  1518.     long            elem;
  1519.     
  1520.     if (id != NoID)
  1521.     {
  1522.         elem = Find_Elem(id);
  1523.         if (elem == NIL)
  1524.             err = qErr;
  1525.         else
  1526.         {
  1527.             err = noErr;
  1528.  
  1529.             Read_iRec(elem, &iRec);
  1530.  
  1531.             if (iRec.previous == NIL)
  1532.                 header.iRoot = iRec.next;
  1533.             else
  1534.             {
  1535.                 Read_iRec(iRec.previous, &iRec2);
  1536.                 iRec2.next = iRec.next;
  1537.                 Write_iRec(iRec.previous, &iRec2);
  1538.             }
  1539.  
  1540.             if (iRec.next != NIL)
  1541.             {
  1542.                 Read_iRec(iRec.next, &iRec2);
  1543.                 iRec2.previous = iRec.previous;
  1544.                 Write_iRec(iRec.next, &iRec2);
  1545.             }
  1546.             
  1547.             Dispose_iRec(elem);
  1548.             Write_Header();
  1549.         }
  1550.     }
  1551. } // Delete_Index
  1552.  
  1553.  
  1554. /*******************************************************************************
  1555.  * Find_Index
  1556.  *
  1557.  *******************************************************************************/
  1558.  
  1559. pascal ID_Type Find_Index(Index_Type index, ID_Type id)
  1560. {
  1561.     iRecType        iRec;
  1562.     long            elem;
  1563.     short            len;
  1564.     
  1565.     err = noErr;
  1566.     if (id == NoID)
  1567.         elem = header.iRoot;
  1568.     else
  1569.         elem = Find_Elem(id);
  1570.     len = index[0];
  1571.     while (elem != NIL)
  1572.     {
  1573.         Read_iRec(elem, &iRec);
  1574.         if (Compare_Strs(&(index[1]), &(iRec.index[1]), le